In the fields of image processing or speech processing, a process is performed in which a registered pattern most similar to an input pattern is searched for from a database that stores a plurality of registered patterns. The process is called pattern retrieval.
Patterns are often represented as feature vectors. A search system performing pattern retrieval calculates the similarity between a feature vector of an input pattern and a feature vector of each registered pattern. The search system then outputs a registered pattern that has a high degree of similarity as a result of the search.
If the number of registered patterns in the database is huge, simple repetition of calculation of the degree of similarity between an input pattern and registered patterns by the search system requires a huge computation cost. To avoid this, a method for speeding up the search process is required.
Methods for speeding up the search process are mainly classified into two types. One method is approximate nearest neighbor search and the other method is cascading.
Approximate nearest neighbor search, represented by Locally Sensitive Hashing (LSH) or Spectral Hashing, will be described first. In the approximate nearest neighbor search, a search system transforms a feature vector into an index and calculates the degree of similarity between an input pattern and each of only those registered patterns that have the same index as the input pattern. This reduces the number of similarity calculations required to be performed by the search system, thereby enabling the search system to perform faster search. In such a search method, the accuracy and speed of search largely depend on how indices are created. PTL1 and PTL2 disclose examples of the method of this type. Approximate nearest neighbor search can be explained as above.
Cascading will be described as following. In the cascading, a search system uses low-dimensional feature vectors to calculate degrees of similarity and rejects registered patterns that have the degrees of similarity lower than or equal to a threshold. The search system repeats the operation and calculates, by using all dimensions, the degrees of similarity of only registered patterns that finally have not been rejected. Because much of the registered data are rejected by similarity calculation performed with low dimensions, the search system can perform fast search. While the threshold is typically determined through learning in advance, the threshold may be determined in accordance with registered patterns as in the search method disclosed in PTL3, for example. Cascading can be explained as above.